package 力扣_链表.面试常考;

/**
 * @author zx
 * @create 2022-09-12 15:21
 */
public class 排序链表_148 {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){//注意这个递归出口条件
            return head;
        }
        ListNode mid = getMid(head);
        ListNode head2 = mid.next;
        mid.next = null;//截取前半部分的子链表
        //递归的排序两个子链表
        //走完下述过程,两个子链表将有序
        ListNode list1 = sortList(head);
        ListNode list2 = sortList(head2);
        return merge(list1,list2);
    }
    //merge：合并两个子链表为一个链表,return新的头节点
    private ListNode merge(ListNode list1,ListNode list2){
        ListNode dummyHead = new ListNode(5001);
        ListNode temp = dummyHead;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                temp.next = list1;
                list1 = list1.next;
            }else if(list1.val >= list2.val){
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null ? list2 : list1;
        return dummyHead.next;
    }
    //寻找链表的中间节点,使用快慢指针
    private ListNode getMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
